package ACWing.mathematicalknowledge.快速幂;

import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2023/1/12 16:58
 */
public class FastExponentiationInverse {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        while (n-->0){
            int a=sc.nextInt();
            int p=sc.nextInt();
            if(a%p==0){//不互为质数不符合定义无解（不是质数不符合费马小定理）
                System.out.println("impossible");
            }else {
                System.out.println(qmi(a, p - 2, p));
            }

        }
    }
    public static int qmi(int a,int k,int p){
        int res=1;
        while (k>0){
            if((k&1)==1){
                res= (int)((long)res*a%p);
            }
            k=k>>1;
            a=(int) ((long)a*a%p);
        }
        return res;
    }
}
